package practise.alogrithm.introductionToAlogrithm.dataStructures;


import practise.alogrithm.introductionToAlogrithm.LinkedListBuilder;
import practise.alogrithm.introductionToAlogrithm.ListNode;

import java.util.List;

/**
 * todo rewrite the reverse in loop again.
 */
public class LinkedListReverser {
    public static  <T> ListNode<T> reverseInRecursive(ListNode<T> listNode){
       if(listNode.getNext()==null){
           // we use the return there as the new head
           return listNode;
       }
       // we need a param record the next, and when the current will be the head,then inactually, the next is the head
        ListNode<T> next = listNode.getNext();
        //then the head we will get from method in recursively
        ListNode<T> head = reverseInRecursive(next);
        //we assemble the new list here
        //reverse the precede node
        next.setNext(listNode);
        //cut off the link for the linkNode
        listNode.setNext(null);
        return head;

    }

    /**
     *
     * @param listNode
     * @param <T>
     * @return
     */
    public static <T> ListNode reverseInLoop(ListNode<T> listNode){
       //we need a previous pointer for saving the result
        ListNode<T> previous = listNode;

        //prepare for the reverse process
        listNode = listNode.getNext();
        //then cut off the first connection between first and second
        previous.setNext(null);
        for(ListNode<T> temp = listNode;listNode.getNext()!=null;previous=temp,temp=listNode){
            listNode = listNode.getNext();
            temp.setNext(previous);

        }
        //in the end connect the last one to previous
        listNode.setNext(previous);
        return listNode;
    }

    public static void main(String[] args){
       ListNode<Integer> listNode = LinkedListBuilder.buildLinkedListFromArray(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8});
        ListNode<Integer> head = reverseInRecursive(listNode);

        while(head.getNext()!=null){
            System.out.print("["+head.getValue()+"]");

            head = head.getNext();
        }

        listNode = LinkedListBuilder.buildLinkedListFromArray(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8});
        ListNode<Integer> listNode1 = reverseInLoop(listNode);

        while(listNode1.getNext()!=null){
            System.out.print("["+listNode1.getValue()+"]");

            listNode1 = listNode1.getNext();
        }
    }
}
